package com.solution;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 * @author LiYongKui
 * @version 1.0
 * @date 2021/1/26 17:19
 */
public class Solution0022 {

    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result,new StringBuilder(),0,0,n);
        return result;
    }

    private static void backtrack(List<String> result, StringBuilder sb, int l, int r, int n) {
        if(sb.length()  == n * 2){
            result.add(sb.toString());
        }
        if (l < n) {
            sb.append("(");
            backtrack(result,sb,l+1,r,n);
            sb.deleteCharAt(sb.length() -1);
        }
        if (l > r){
            sb.append(")");
            backtrack(result,sb,l,r+1,n);
            sb.deleteCharAt(sb.length() -1);
        }
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

}
